import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

// 二叉搜索树与双向链表
// https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null){
            return null;
        }
        List<TreeNode> tmpList = new ArrayList<>();
        InOrder(pRootOfTree,tmpList);
        TreeNode head = tmpList.get(0);
        TreeNode ptr = head;
        head.left = null;
        for (int i = 1; i <tmpList.size() ; i++) {
            ptr.right = tmpList.get(i);
            tmpList.get(i).left = ptr;
            ptr = ptr.right;
        }
        return head;



    }

    private void InOrder1(TreeNode pRootOfTree,List<TreeNode> tmpList){
        if (pRootOfTree == null){
            return;
        }
        InOrder1(pRootOfTree.left,tmpList);
        tmpList.add(pRootOfTree);
        InOrder1(pRootOfTree.right,tmpList);




    }


    public TreeNode Convert1(TreeNode root) {
        if (root == null){
            return null;
        }
        List<TreeNode> tmpList = new ArrayList<>();
        InOrder(root,tmpList);
        TreeNode head = tmpList.get(0);
        TreeNode ptr = head;
        head.left = null;
        for (int i = 1; i <tmpList.size() ; i++) {
            head.right = tmpList.get(1);
            tmpList.get(1).left = ptr;
            ptr = ptr.right;

        }
        return head;
    }
public void InOrder(TreeNode root,List<TreeNode> tmpList){
        if (root == null){
            return;
        }
        InOrder(root.left,tmpList);
        tmpList.add(root);
        InOrder(root.right,tmpList);

}

}
